from heapq import heappush, heappushpop

"""

方法：使用两个堆来维护数据流的中位数，left是一个最大堆（通过存储负数实现），right是一个最小堆。通过保持两个堆的大小平衡来快速获取中位数。

Args:
    num (int): 要添加到数据流中的数字

Returns:
    float: 当前数据流的中位数

Time:
    addNum: O(log n) - 每次插入需要堆操作
    findMedian: O(1) - 直接访问堆顶元素

Space:
    O(n) - 需要存储所有输入数字

"""
class MedianFinder:

    def __init__(self):
       self.left = [] # 入堆的元素取相反数，变成最大堆
       self.right = [] #最小堆

    def addNum(self, num: int) -> None:
        if len(self.left) == len(self.right):
            heappush(self.left, -heappushpop(self.right, num))
        else:
            heappush(self.right, -heappushpop(self.left, -num))

    def findMedian(self) -> float:
        if len(self.left) > len(self.right):
            return -self.left[0]
        else:
            return (self.right[0] - self.left[0]) / 2


# Your MedianFinder object will be instantiated and called as such:
# obj = MedianFinder()
# obj.addNum(num)
# param_2 = obj.findMedian()